package com.wangyadong.hobby.schedule.jobtask.dsa.binaryTree.da;

import java.util.Comparator;
import java.util.Random;

public class BinarySearchTree<T> {

    //跟节点
    private TreeNode root;


    public BinarySearchTree() {

    }

    //内部类
    private static class TreeNode<T> {
        private T t;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(T t, TreeNode left, TreeNode right) {
            this.left = left;
            this.right = right;
            this.t = t;
        }
    }


    public boolean contains(T t, TreeNode treeNode) {
        if (t == null || treeNode == null) {
            return false;
        }
        Comparable comparable = (Comparable) t;
        int compareResult = comparable.compareTo(treeNode.t);
        if (compareResult < 0) {
            return contains(t, treeNode.left);
        } else if (compareResult > 0) {
            return contains(t, treeNode.right);
        } else {
            return true;
        }
    }

    public TreeNode insert(T t) {
        return root = insert(t, root);
    }

    public TreeNode remove(T t) {
        return root = remove(t, root);
    }

    public TreeNode insert(T t, TreeNode treeNode) {
        if (t == null) {
            return null;
        }
        if (treeNode == null) {
            return new TreeNode(t, null, null);
        }
        Comparable comparable = (Comparable) t;
        int compareResult = comparable.compareTo(treeNode.t);
        if (compareResult < 0) {
            treeNode.left = insert(t, treeNode.left);
        } else if (compareResult > 0) {
            treeNode.right = insert(t, treeNode.right);
        } else {
            // return null;
            ;
        }
        return treeNode;
    }


    public TreeNode findMin(TreeNode treeNode) {
        if (treeNode == null) {
            return treeNode;
        }
        if (treeNode.left == null) {
            return treeNode;
        }
        return findMin(treeNode.left);
    }

    public TreeNode findMax(TreeNode treeNode) {
        if (treeNode == null) {
            return treeNode;
        }
        if (treeNode.right == null) {
            return treeNode;
        }
        return findMax(treeNode.left);
    }


    public TreeNode remove(T value, TreeNode treeNode) {
        if (treeNode == null) {
            return null;
        }
        Comparable comparable = (Comparable) value;
        int compareResult = comparable.compareTo(treeNode.t);
        if (compareResult < 0) {
            treeNode.left = remove(value, treeNode.left);
        } else if (compareResult > 0) {
            treeNode.right = remove(value, treeNode.right);
        } else if (treeNode.left != null && treeNode.right != null) {
            treeNode.t = findMin(treeNode.right).t;
            treeNode.right = remove(value, treeNode.right);
        } else {
            treeNode = (treeNode.left != null) ? treeNode.left : treeNode.right;
        }
        return treeNode;
    }

    public void printTree(TreeNode node) {
        if (node != null) {
            System.out.println(node.t);
            printTree(node.left);
            printTree(node.right);
        }
    }

    public static void main(String[] args) {
        BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
        for (int i = 5000; i > 0; i--) {
//            binarySearchTree.insert(new Random(System.nanoTime()).nextInt());
            binarySearchTree.insert(i);
        }
        System.out.println("=================================================");
        System.out.println("========================remove=========================");
        for (int i = 0; i < 500; i++) {
            binarySearchTree.remove(i);
        }
        binarySearchTree.printTree(binarySearchTree.root);

    }
}
